package name.huzhenbo.java.algorithm.tree;

/**
 * ASL (Average search length): (numberOfNodesInLevel1 * 1 + .... numberOfNodesInLeveln * n) / number of nodes
 */
class BinarySearchTree {
    private Node root;

    public void insert(int val) {
        Node node = new Node(val, null, null);
        if (root == null) {
            root = node;
        } else {
            _insert(root, node);
        }
    }

    private void _insert(Node currentNode, Node node) {
        if (currentNode.getVal() > node.val) {
            if (currentNode.getLeft() == null) currentNode.setLeft(node);
            else _insert(currentNode.getLeft(), node);
        } else if (currentNode.getVal() < node.val) {
            if (currentNode.getRight() == null) currentNode.setRight(node);
            else _insert(currentNode.getRight(), node);
        }
    }

    public void traverse() {
        _traverse(root);
    }

    private void _traverse(Node node) {
        if (node == null) {
            return;
        }
        _traverse(node.getLeft());
        System.out.println(node.getVal());
        _traverse(node.getRight());
    }

    protected class Node {
        private int val;
        private Node left;
        private Node right;

        public Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public int getVal() {
            return val;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

    }
}
